public class AVLTree<T extends Comparable<T>> {

    private static class AVLNode<T> {
        T key;
        AVLNode<T> left;
        AVLNode<T> right;
        int height;

        AVLNode(T key){
         this(key,null,null);
        }

        AVLNode (T key,AVLNode<T> lt,AVLNode<T> rt){
            this.key = key;
            this.left = lt;
            this.right = rt;
            height = 0;
        }
    }

    private int height(AVLNode<T> t){
        return t==null?-1:t.height;
    }


    /*
     *左左
    * 1,节点的左节点连上节点
    * 2,节点左节点的右节点变成节点的左节点
    * 3,调整高度
    *
    * */

    private AVLNode<T> rightRotate(AVLNode<T> y){
        AVLNode<T> x = y.left;
        AVLNode<T> t2 = x.right;
        x.right = y;
        y.left = t2;
        y.height = Math.max(y.left.height,y.right.height);
        x.height = Math.max(x.left.height,x.right.height);
        return x;
    }


    private AVLNode<T> leftRotate(AVLNode<T> x){
        AVLNode<T> y = x.right;
        AVLNode<T> t2 = y.left;
        y.left = x;
        x.right = t2;
        x.height = Math.max(x.left.height,x.right.height);
        y.height = Math.max(y.left.height,y.right.height);
        return y;
    }

}
